{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Path Crossing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPathCrossing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #判断路径是否相交"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>path</code>，其中 <code>path[i]</code> 的值可以是 <code>'N'</code>、<code>'S'</code>、<code>'E'</code> 或者 <code>'W'</code>，分别表示向北、向南、向东、向西移动一个单位。</p>\n",
    "\n",
    "<p>你从二维平面上的原点 <code>(0, 0)</code> 处开始出发，按 <code>path</code> 所指示的路径行走。</p>\n",
    "\n",
    "<p>如果路径在任何位置上与自身相交，也就是走到之前已经走过的位置，请返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/06/28/screen-shot-2020-06-10-at-123929-pm.png\" style=\"height: 358px; width: 400px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>path = \"NES\"\n",
    "<strong>输出：</strong>false \n",
    "<strong>解释：</strong>该路径没有在任何位置相交。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/06/28/screen-shot-2020-06-10-at-123843-pm.png\" style=\"height: 339px; width: 400px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>path = \"NESWW\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>该路径经过原点两次。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= path.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>path[i]</code> 为 <code>'N'</code>、<code>'S'</code>、<code>'E'</code> 或 <code>'W'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [path-crossing](https://leetcode.cn/problems/path-crossing/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [path-crossing](https://leetcode.cn/problems/path-crossing/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"NES\"', '\"NESWW\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        visited = set()\n",
    "        cur = (0,0)\n",
    "        visited.add(cur)\n",
    "        for i in path:\n",
    "            if i == 'N':\n",
    "                cur = (cur[0], cur[1]+1)\n",
    "            if i == 'S':\n",
    "                cur = (cur[0], cur[1]-1)\n",
    "            if i == 'E':\n",
    "                cur = (cur[0]+1, cur[1])\n",
    "            if i == 'W':\n",
    "                cur = (cur[0]-1, cur[1])\n",
    "            if cur in visited:\n",
    "                return True\n",
    "            visited.add(cur)\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dic = {}\n",
    "        dic[0] = {0}\n",
    "        x,y = 0,0\n",
    "        for i in path:\n",
    "            if i == \"N\":\n",
    "                y += 1\n",
    "            elif i == \"S\":\n",
    "                y -= 1\n",
    "            elif i == \"W\":\n",
    "                x -= 1\n",
    "            else:\n",
    "                x += 1\n",
    "            if x in dic:\n",
    "                if y in dic[x]:\n",
    "                    return True\n",
    "                else:\n",
    "                    dic[x].add(y)\n",
    "            else:\n",
    "                dic[x] = {y}\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self,path:str)->bool:\n",
    "        dirs={\n",
    "            \"N\":(0,1),\n",
    "            \"S\":(0,-1),\n",
    "            \"W\":(-1,0),\n",
    "            \"E\":(1,0)\n",
    "        }\n",
    "\n",
    "        x,y=0,0\n",
    "        mypath=set([(x,y)])\n",
    "        for ch in path:\n",
    "            dx,dy=dirs[ch]\n",
    "            x,y=x+dx,y+dy\n",
    "            if (x,y) in mypath:\n",
    "                return True\n",
    "            mypath.add((x,y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs={\n",
    "            \"N\":(0,1),\n",
    "            \"S\":(0,-1),\n",
    "            \"E\":(1,0),\n",
    "            \"W\":(-1,0)\n",
    "        }\n",
    "\n",
    "        x,y=0,0\n",
    "        vis=set([(x,y)])\n",
    "        for ch in path:\n",
    "            dx,dy=dirs[ch]\n",
    "            x,y=x+dx,y+dy\n",
    "            if (x,y) in vis:\n",
    "                return True\n",
    "            vis.add((x,y))\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        row = 0\n",
    "        colunm = 0\n",
    "        cnt = Counter()\n",
    "        cnt[(0,0)] = 1\n",
    "        for i in path:\n",
    "            if i == 'N':\n",
    "                colunm += 1\n",
    "            if i == 'S':\n",
    "                colunm -= 1\n",
    "            if i == 'W':\n",
    "                row += 1\n",
    "            if i == 'E':\n",
    "                row -= 1\n",
    "            cnt[(row,colunm)] += 1\n",
    "            if cnt[(row,colunm)] ==2:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs = {\n",
    "            \"N\": (1,0),\n",
    "            \"S\":(-1,0),\n",
    "            \"W\":(0,-1),\n",
    "            \"E\":(0,1),\n",
    "        }\n",
    "\n",
    "        x,y=0,0\n",
    "        vis=set([(x,y)])\n",
    "        for ch in path:\n",
    "            dx,dy=dirs[ch]\n",
    "            x,y=x+dx,y+dy\n",
    "            if (x,y) in vis:\n",
    "                return True\n",
    "            vis.add((x,y))\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        paths=[[0,0]]\n",
    "        for p in path:\n",
    "            pos=paths[-1]\n",
    "            print(pos)\n",
    "            if p=='N':\n",
    "                pos=[pos[0],pos[1]+1]\n",
    "            elif p=='S':\n",
    "                pos=[pos[0],pos[1]-1]\n",
    "            elif p=='E':\n",
    "                pos=[pos[0]+1,pos[1]]\n",
    "            else:\n",
    "                pos=[pos[0]-1,pos[1]]\n",
    "            if pos in paths:\n",
    "                return True\n",
    "            paths.append(pos)\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        points = [[0, 0]]\n",
    "        location = [0, 0]\n",
    "        for direction in path:\n",
    "            if direction == 'N':\n",
    "                location = [location[0], location[1] + 1]\n",
    "            if direction == 'S':\n",
    "                location = [location[0], location[1] - 1]\n",
    "            if direction == 'W':\n",
    "                location = [location[0] - 1, location[1]]\n",
    "            if direction == 'E':\n",
    "                location = [location[0] + 1, location[1]]\n",
    "\n",
    "            if location in points:\n",
    "                return True\n",
    "            else:\n",
    "                points.append(location)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x = 0\n",
    "        y = 0\n",
    "        l1 = set()\n",
    "        l1.add((0,0))\n",
    "        for i in range (len(path)):\n",
    "            if path[i] == \"N\":\n",
    "                y += 1\n",
    "            elif path[i] == \"S\":\n",
    "                y -= 1\n",
    "            elif path[i] == \"E\":\n",
    "                x += 1\n",
    "            elif path[i] == \"W\":\n",
    "                x -= 1\n",
    "            if (x,y) not in l1:\n",
    "                l1.add((x,y))\n",
    "            else:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        d={'N':(0,1),'S':(0,-1),'W':(-1,0),'E':(1,0)}\n",
    "        x,y=0,0\n",
    "        vis=set([(x,y)])\n",
    "        for a in path:\n",
    "            dx,dy=d[a]\n",
    "            x+=dx\n",
    "            y+=dy\n",
    "            if (x,y) in vis:\n",
    "                return True\n",
    "            vis.add((x,y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        v, x, y = {(0, 0)}, 0, 0\n",
    "        d = dict(N=(0, 1), S=(0, -1), E=(1, 0), W=(-1, 0))\n",
    "        for c in path:\n",
    "            x += d[c][0]\n",
    "            y += d[c][1]\n",
    "            if (x, y) in v:\n",
    "                return True\n",
    "            v.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        der_dict = {'N':(0,1),'E':(1,0),'S':(0,-1),'W':(-1,0)}\n",
    "        path_list = [(0,0)]\n",
    "        for i in path:\n",
    "            res = ((path_list[-1][0]+der_dict[i][0]),(path_list[-1][1]+der_dict[i][1]))\n",
    "            if res not in path_list:\n",
    "                path_list.append(res)\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        visited = {(0, 0)}\n",
    "        d = {'N':(0, 1), 'E':(1, 0), 'W':(-1, 0), 'S':(0, -1)}\n",
    "        x, y = 0, 0\n",
    "        for dir in path:\n",
    "            x += d[dir][0]\n",
    "            y += d[dir][1]\n",
    "            if (x, y) in visited:\n",
    "                return True\n",
    "            visited.add((x, y))\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        #已经走过的点\n",
    "        crossPathList = [(0,0)]\n",
    "        #设起点是0.0\n",
    "        direction = {\"N\":(0,1),\"S\":(0,-1),\"E\":(1,0),\"W\":(-1,0)}\n",
    "        x = y = 0\n",
    "        for p in path:\n",
    "            x += direction[p][0]\n",
    "            y += direction[p][1]\n",
    "\n",
    "            if (x, y) in crossPathList:\n",
    "                return True\n",
    "            else:\n",
    "                crossPathList.append((x, y))\n",
    "\n",
    "        return False\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x,y = 0,0\n",
    "        ret = [(0,0)]\n",
    "        for i in path:\n",
    "            if i == 'N':\n",
    "                y += 1\n",
    "            elif i == 'S':\n",
    "                y -= 1\n",
    "            elif i == 'E':\n",
    "                x += 1\n",
    "            elif i == 'W':\n",
    "                x -= 1\n",
    "            if (x,y) in ret:\n",
    "                return True\n",
    "            else:\n",
    "                ret.append((x,y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs = {\n",
    "            \"N\": (-1, 0),\n",
    "            \"S\": (1, 0),\n",
    "            \"W\": (0, -1),\n",
    "            \"E\": (0, 1),\n",
    "        }\n",
    "        \n",
    "        x, y = 0, 0\n",
    "        vis = set([(x, y)])\n",
    "        for ch in path:\n",
    "            dx, dy = dirs[ch]\n",
    "            x, y = x + dx, y + dy\n",
    "            if (x, y) in vis:\n",
    "                return True\n",
    "            vis.add((x, y))\n",
    "\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        tmpset = set()\n",
    "        x, y = 0, 0\n",
    "        tmpset.add((x, y))\n",
    "        for item in path:\n",
    "            match item:\n",
    "                case \"N\":\n",
    "                    y += 1\n",
    "                case \"S\":\n",
    "                    y -= 1\n",
    "                case \"E\":\n",
    "                    x += 1\n",
    "                case \"W\":\n",
    "                    x -= 1\n",
    "        \n",
    "            if (x, y) in tmpset:\n",
    "                return True\n",
    "            else:\n",
    "                tmpset.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs = {\n",
    "            \"N\": (-1, 0),\n",
    "            \"S\": (1, 0),\n",
    "            \"W\": (0, -1),\n",
    "            \"E\": (0, 1),\n",
    "        }\n",
    "        \n",
    "        x, y = 0, 0\n",
    "        vis = set([(x, y)])\n",
    "        for ch in path:\n",
    "            dx, dy = dirs[ch]\n",
    "            x, y = x + dx, y + dy\n",
    "            if (x, y) in vis:\n",
    "                return True\n",
    "            vis.add((x, y))\n",
    "\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        der_dict = {'N':(0,1),'E':(1,0),'S':(0,-1),'W':(-1,0)}\n",
    "        path_list = [[0,0]]\n",
    "        for i in path:\n",
    "            res = [i + j for i, j in zip(path_list[-1],der_dict[i])]\n",
    "            if res not in path_list:\n",
    "                path_list.append(res)\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x,y=0,0\n",
    "        sets=set()\n",
    "        sets.add((0,0))\n",
    "        for d in path:\n",
    "            if d=='N':\n",
    "                x=x\n",
    "                y=y+1\n",
    "            elif d=='S':\n",
    "                x=x\n",
    "                y=y-1\n",
    "            elif d=='W':\n",
    "                x=x-1\n",
    "                y=y\n",
    "            else :\n",
    "                x=x+1\n",
    "                y=y\n",
    "            if (x,y) in sets:\n",
    "                    return True\n",
    "            # print(x,y,sets)\n",
    "            sets.add((x,y))\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# python3\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        paths = [(0,0)]\n",
    "        x,y = 0,0\n",
    "        for i in path:\n",
    "            if i == 'N':\n",
    "                x -= 1\n",
    "            elif i == 'S':\n",
    "                x += 1\n",
    "            elif i == 'E':\n",
    "                y += 1\n",
    "            else:\n",
    "                y -= 1\n",
    "            if (x,y) in paths:\n",
    "                return True\n",
    "            paths.append((x,y))\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        temp=[0,0]\n",
    "        list=[[0,0]]\n",
    "        for i in path:\n",
    "            if i=='N':\n",
    "                temp[1]+=1\n",
    "            elif i=='S':\n",
    "                temp[1]-=1\n",
    "            elif i=='W':\n",
    "                temp[0]-=1\n",
    "            else:\n",
    "                temp[0]+=1\n",
    "            if temp in list:\n",
    "                return True\n",
    "            else:\n",
    "                list.append(temp[:])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        der_dict = {'N': (0, 1), 'E': (1, 0), 'S': (0, -1), 'W': (-1, 0)}\n",
    "        path_list = [[0, 0]]\n",
    "        for i in path:\n",
    "            res = [i + j for i, j in zip(path_list[-1], der_dict[i])]\n",
    "            if res in path_list:\n",
    "                return True\n",
    "            else:\n",
    "                path_list.append(res)\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs = {\n",
    "            'N': (-1, 0),\n",
    "            'S': (1, 0),\n",
    "            'W': (0, -1),\n",
    "            'E': (0, 1),\n",
    "        }\n",
    "        x, y = 0, 0\n",
    "        vis = set([(x, y)])\n",
    "        for ch in path:\n",
    "            dx, dy = dirs[ch]\n",
    "            x, y = x + dx, y + dy\n",
    "            if (x, y) in vis:\n",
    "                return True\n",
    "            vis.add((x, y))\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs = {\n",
    "            \"N\": (0, 1),\n",
    "            \"S\": (0, -1),\n",
    "            \"W\": (-1, 0),\n",
    "            \"E\": (1, 0)\n",
    "        }\n",
    "\n",
    "        x, y = 0, 0\n",
    "        vis = set([(x, y)])\n",
    "        for ch in path:\n",
    "            dx, dy = dirs[ch]\n",
    "            x, y = x + dx, y + dy\n",
    "            if (x, y) in vis:\n",
    "                return True\n",
    "            vis.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRE = {'N':(0, 1), 'S':(0, -1), 'E':(1, 0), 'W':(-1, 0)}\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        start = [0, 0]\n",
    "        seen = {(0, 0)}\n",
    "        for d in path:\n",
    "            x, y = DIRE[d]\n",
    "            start[0] += x\n",
    "            start[1] += y\n",
    "            t = tuple(start)\n",
    "            if t in seen:\n",
    "                return True\n",
    "            seen.add(t)\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs = {\"N\": (1, 0), \"S\": (-1, 0), \"W\": (0, -1), \"E\": (0, 1)}\n",
    "        x, y = 0, 0\n",
    "        ans = set([(x, y)])\n",
    "        for ch in path:\n",
    "            dx, dy = dirs[ch]\n",
    "            x , y = x + dx,y + dy\n",
    "            if (x, y) in ans:\n",
    "                return True\n",
    "            ans.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        c = 0\n",
    "        d = 0\n",
    "        e = {(0, 0): 0}\n",
    "        flag = 0\n",
    "        for x in path:\n",
    "            if x == \"N\":\n",
    "                c = c + 1\n",
    "            elif x == \"S\":\n",
    "                c = c - 1\n",
    "            elif x == \"E\":\n",
    "                d = d + 1\n",
    "            else:\n",
    "                d = d - 1\n",
    "            if (c, d) in e:\n",
    "                flag = 1\n",
    "                break\n",
    "            else:\n",
    "                e[(c, d)] = 0\n",
    "        return flag == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRE = {'N':(0, 1), 'S':(0, -1), 'E':(1, 0), 'W':(-1, 0)}\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x = y = 0\n",
    "        seen = {(0, 0)}\n",
    "        for d in path:\n",
    "            dx, dy = DIRE[d]\n",
    "            x += dx\n",
    "            y += dy\n",
    "            if (x, y) in seen:\n",
    "                return True\n",
    "            seen.add((x, y))\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x, y, se = 0, 0, {(0, 0)}\n",
    "        for c in path:\n",
    "            if   c == 'N': y += 1\n",
    "            elif c == 'E': x += 1\n",
    "            elif c == 'S': y -= 1\n",
    "            else         : x -= 1\n",
    "            if (x, y) in se: return True\n",
    "            se.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs = {\n",
    "            \"N\": (1, 0),\n",
    "            \"S\": (-1, 0),\n",
    "            \"W\": (0, -1),\n",
    "            \"E\": (0, 1),\n",
    "        }\n",
    "        \n",
    "        x, y = 0, 0\n",
    "        vis = set()\n",
    "        vis.add((x, y))\n",
    "        for ch in path:\n",
    "            dx, dy = dirs[ch]\n",
    "            x, y = x + dx, y + dy\n",
    "            if (x, y) in vis:\n",
    "                return True\n",
    "            vis.add((x, y))\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        pos = [0, 0]\n",
    "        s = set()\n",
    "        s.add(tuple(pos))\n",
    "        for ch in path:\n",
    "            if ch == 'N':\n",
    "                pos[1] += 1\n",
    "            elif ch == 'S':\n",
    "                pos[1]  -= 1\n",
    "            elif ch == 'E':\n",
    "                pos[0] += 1\n",
    "            else:\n",
    "                pos[0] -= 1\n",
    "            if tuple(pos) in s:\n",
    "                return True\n",
    "            s.add(tuple(pos))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x,y=0,0\n",
    "        a = [(0,0)]\n",
    "        for i in path:\n",
    "            if i == 'N':\n",
    "                y += 1\n",
    "            if i == 'S':\n",
    "                y -= 1\n",
    "            if i == 'E':\n",
    "                x += 1\n",
    "            if i == 'W':\n",
    "                x -= 1\n",
    "            if (x,y) in a:\n",
    "                return True\n",
    "            else:\n",
    "                a.append((x,y))\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        der_dict = {'N':(0,1),'E':(1,0),'S':(0,-1),'W':(-1,0)}\n",
    "        path_list = [[0,0]]\n",
    "        for i in path:\n",
    "            res = [i + j for i, j in zip(path_list[-1],der_dict[i])]\n",
    "            if res not in path_list:\n",
    "                path_list.append(res)\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x,y=0,0\n",
    "        sets=set()\n",
    "        sets.add((0,0))\n",
    "        for d in path:\n",
    "            if d=='N':\n",
    "                x=x\n",
    "                y=y+1\n",
    "            elif d=='S':\n",
    "                x=x\n",
    "                y=y-1\n",
    "            elif d=='W':\n",
    "                x=x-1\n",
    "                y=y\n",
    "            else :\n",
    "                x=x+1\n",
    "                y=y\n",
    "            if (x,y) in sets:\n",
    "                    return True\n",
    "            # print(x,y,sets)\n",
    "            sets.add((x,y))\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        re = [[0, 0]]\n",
    "        cur = [0, 0]\n",
    "        for i in range(len(path)):\n",
    "            if path[i] == 'N':\n",
    "                cur = [cur[0], cur[1] + 1]\n",
    "            elif path[i] == 'S':\n",
    "                cur = [cur[0], cur[1] - 1]\n",
    "            elif path[i] == 'W':\n",
    "                cur = [cur[0] - 1, cur[1]]\n",
    "            elif path[i] == 'E':\n",
    "                cur = [cur[0] + 1, cur[1]]\n",
    "            if cur in re :\n",
    "                return True\n",
    "            else:\n",
    "                re.append(cur)\n",
    "        return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        der_dict = {'N': (0, 1), 'E': (1, 0), 'S': (0, -1), 'W': (-1, 0)}\n",
    "        path_list = [[0, 0]]\n",
    "        for i in path:\n",
    "            res = [i + j for i, j in zip(path_list[-1], der_dict[i])]\n",
    "            if res in path_list:\n",
    "                return True\n",
    "            else:\n",
    "                path_list.append(res)\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs = {\n",
    "            \"N\": (-1, 0),\n",
    "            \"S\": (1, 0),\n",
    "            \"W\": (0, -1),\n",
    "            \"E\": (0, 1),\n",
    "        }\n",
    "        \n",
    "        x, y = 0, 0\n",
    "        vis = set([(x, y)])\n",
    "        for ch in path:\n",
    "            dx, dy = dirs[ch]\n",
    "            x, y = x + dx, y + dy\n",
    "            if (x, y) in vis:\n",
    "                return True\n",
    "            vis.add((x, y))\n",
    "\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        der_dict = {'N':(0,1),'E':(1,0),'S':(0,-1),'W':(-1,0)}\n",
    "        path_list = [[0,0]]\n",
    "        for i in path:\n",
    "            res = [i + j for i, j in zip(path_list[-1],der_dict[i])]\n",
    "            if res not in path_list:\n",
    "                path_list.append(res)\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        # lens = len(path)\n",
    "        # lenc = len(set(path))\n",
    "        # if lens > lenc:\n",
    "        #     return True\n",
    "        # else:\n",
    "        #     return False\n",
    "        count = 0\n",
    "        dics = {\n",
    "            \"N\":(0,1),\n",
    "            \"S\":(0,-1),\n",
    "            \"W\":(-1,0),\n",
    "            \"E\":(1,0)\n",
    "        }\n",
    "        x = y = 0\n",
    "        ss = set([(x,y)])\n",
    "        for i in path:\n",
    "            sx, sy = dics[i]\n",
    "            x, y = x + sx, y + sy\n",
    "            if(x, y) in ss:\n",
    "                return True\n",
    "            ss.add((x,y))\n",
    "        return False\n",
    "\n",
    "\n",
    "           \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        der_dict = {'N':(0,1),'E':(1,0),'S':(0,-1),'W':(-1,0)}\n",
    "        path_list = [[0,0]]\n",
    "        for i in path:\n",
    "            res = [i + j for i, j in zip(path_list[-1],der_dict[i])]\n",
    "            if res not in path_list:\n",
    "                path_list.append(res)\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        pathList, originPt = [[0, 0]], [0, 0]\n",
    "        for p in path:\n",
    "            if p == \"N\":\n",
    "                originPt[1] += 1\n",
    "            if p == \"S\":\n",
    "                originPt[1] -= 1\n",
    "            if p == \"E\":\n",
    "                originPt[0] += 1\n",
    "            if p == \"W\":\n",
    "                originPt[0] -= 1\n",
    "            if originPt in pathList:\n",
    "                return True\n",
    "            else:\n",
    "                pathList.append([originPt[0], originPt[1]])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs = {\n",
    "            \"N\" : (1, 0),\n",
    "            \"S\" : (-1, 0),\n",
    "            \"W\" : (0, -1),\n",
    "            \"E\" : (0, 1),\n",
    "        }\n",
    "        x, y = 0, 0\n",
    "        vis = set()\n",
    "        vis.add((x, y))\n",
    "        for ch in path:\n",
    "            dx, dy = dirs[ch]\n",
    "            x, y = x + dx, y + dy\n",
    "            if (x, y) in vis:\n",
    "                return True\n",
    "            vis.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        s,dic = {(0,0)}, {'N':[0,1], 'S':[0,-1], 'E':[1,0], 'W':[-1,0]}\n",
    "        x,y = 0,0\n",
    "        for i in path:\n",
    "            x, y = x+dic[i][0], y+dic[i][1]\n",
    "            if (x,y) in s:\n",
    "                return True\n",
    "            else:\n",
    "                s.add((x,y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        point = [0,0]\n",
    "        points = ['[0, 0]']\n",
    "        for p in path:\n",
    "            if p==\"N\":point[1]=point[1]+1\n",
    "            elif p==\"S\":point[1]=point[1]-1\n",
    "            elif p==\"E\":point[0]=point[0]+1\n",
    "            elif p==\"W\":point[0]=point[0]-1\n",
    "            #print(point)\n",
    "            tmp = str(point)\n",
    "            #print(tmp)\n",
    "            if tmp in points:return True\n",
    "            else:points.append(tmp)\n",
    "            #print(points)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        l = [(0, 0)]\n",
    "        x, y = 0, 0\n",
    "        for i in path:\n",
    "            if i == 'N':\n",
    "                y += 1\n",
    "            elif i == 'S':\n",
    "                y -= 1\n",
    "            elif i == 'E':\n",
    "                x += 1\n",
    "            elif i == 'W':\n",
    "                x -= 1\n",
    "            if (x, y) in l:\n",
    "                return True\n",
    "            else:\n",
    "                l.append((x, y))\n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x, y, se = 0, 0, {(0, 0)}\n",
    "        for c in path:\n",
    "            if   c == 'N': y += 1\n",
    "            elif c == 'E': x += 1\n",
    "            elif c == 'S': y -= 1\n",
    "            else         : x -= 1\n",
    "            if (x, y) in se: return True\n",
    "            se.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs = {\n",
    "            \"N\": (-1, 0),\n",
    "            \"S\": (1, 0),\n",
    "            \"W\": (0, -1),\n",
    "            \"E\": (0, 1),\n",
    "        }\n",
    "        x, y = 0, 0\n",
    "        visited = set([(x, y)])\n",
    "        for ch in path:\n",
    "            dx, dy = dirs[ch]\n",
    "            x, y = x + dx, y + dy\n",
    "            if (x, y) in visited:\n",
    "                return True\n",
    "            visited.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x, y = 0, 0\n",
    "        s = set()\n",
    "        s.add((x, y))\n",
    "        for ch in path:\n",
    "            if ch == 'N':\n",
    "                y += 1\n",
    "            elif ch == 'S':\n",
    "                y  -= 1\n",
    "            elif ch == 'E':\n",
    "                x += 1\n",
    "            else:\n",
    "                x -= 1\n",
    "            if (x, y) in s:\n",
    "                return True\n",
    "            s.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self,path: str) -> bool:\n",
    "        pos = [0, 0]\n",
    "        his = [(0,0)]\n",
    "        for i in path:\n",
    "            if i == \"N\":\n",
    "                pos[1] += 1\n",
    "            elif i == \"S\":\n",
    "                pos[1] -= 1\n",
    "            elif i == \"E\":\n",
    "                pos[0] += 1\n",
    "            else:\n",
    "                pos[0] -= 1\n",
    "            pos_temp=(pos[0],pos[1])\n",
    "            if pos_temp in his:\n",
    "                return True\n",
    "            else:\n",
    "                his.append(pos_temp)\n",
    "        return  False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        save = set()\n",
    "        p = [0,0]\n",
    "        save.add(tuple(p))\n",
    "        for i in path:\n",
    "            if i == 'N':\n",
    "                p[1] += 1\n",
    "            elif i == 'S':\n",
    "                p[1] -= 1\n",
    "            elif i == 'W':\n",
    "                p[0] -= 1\n",
    "            else:\n",
    "                p[0] += 1\n",
    "            if tuple(p) in save:\n",
    "                return True\n",
    "            save.add(tuple(p))\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        der_dict = {'N':(0,1),'E':(1,0),'S':(0,-1),'W':(-1,0)}\n",
    "        path_list = [(0,0)]\n",
    "        for i in path:\n",
    "            res = ((path_list[-1][0]+der_dict[i][0]),(path_list[-1][1]+der_dict[i][1]))\n",
    "            if res not in path_list:\n",
    "                path_list.append(res)\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        point = [0,0]\n",
    "        points = [str(point)]\n",
    "        for p in path:\n",
    "            if p==\"N\":point[1]=point[1]+1\n",
    "            elif p==\"S\":point[1]=point[1]-1\n",
    "            elif p==\"E\":point[0]=point[0]+1\n",
    "            elif p==\"W\":point[0]=point[0]-1\n",
    "            #print(point)\n",
    "            tmp = str(point)\n",
    "            #print(tmp)\n",
    "            if tmp in points:return True\n",
    "            else:points.append(tmp)\n",
    "            #print(points)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "\n",
    "        x, y = 0, 0\n",
    "        res = [[0, 0]]\n",
    "        tmp = []\n",
    "        lens = len(path)\n",
    "\n",
    "        for s in path:\n",
    "            if s == 'N':\n",
    "                y += 1\n",
    "            elif s == 'S':\n",
    "                y += -1\n",
    "            elif s == 'W':\n",
    "                x += -1\n",
    "            elif s == 'E':\n",
    "                x += 1\n",
    "            tmp = [x,y]\n",
    "                        \n",
    "            if tmp in res:\n",
    "                return True\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "        \n",
    "        return False\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x, y, se = 0, 0, {(0, 0)}\n",
    "        for c in path:\n",
    "            if   c == 'N': y += 1\n",
    "            elif c == 'E': x += 1\n",
    "            elif c == 'S': y -= 1\n",
    "            else         : x -= 1\n",
    "            if (x, y) in se: return True\n",
    "            se.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        crossing = set()\n",
    "        crossing.add((0, 0))\n",
    "        x, y = 0, 0\n",
    "        temp = {\"N\": [0, 1], \"S\": [0, -1], \"E\": [1, 0], \"W\": [-1, 0]}\n",
    "        for i in path:\n",
    "            x += temp[i][0]\n",
    "            y += temp[i][1]\n",
    "            if (x, y) in crossing:\n",
    "                return True\n",
    "            crossing.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        der_dict = {'N': (0, 1), 'E': (1, 0), 'S': (0, -1), 'W': (-1, 0)}\n",
    "        path_list = [[0, 0]]\n",
    "        for i in path:\n",
    "            res = [i + j for i, j in zip(path_list[-1], der_dict[i])]\n",
    "            if res in path_list:\n",
    "                return True\n",
    "            else:\n",
    "                path_list.append(res)\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs = {\n",
    "            \"N\":(-1,0),\n",
    "            \"S\":(1,0),\n",
    "            \"W\":(0,-1),\n",
    "            \"E\":(0,1),\n",
    "        }\n",
    "\n",
    "        x,y = 0,0\n",
    "        vis = set([(x,y)])\n",
    "        for ch in path:\n",
    "            dx,dy = dirs[ch]\n",
    "            x,y = x+dx,y+dy\n",
    "            if(x,y) in vis:\n",
    "                return True\n",
    "            vis.add((x,y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        r=[[0,0]]\n",
    "        directions=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        for i in path:\n",
    "            if i=='E':\n",
    "                if [r[-1][0],r[-1][1]+1] in r:\n",
    "                    return True\n",
    "                r.append([r[-1][0],r[-1][1]+1])\n",
    "            elif i=='S':\n",
    "                if [r[-1][0]+1,r[-1][1]] in r:\n",
    "                    return True\n",
    "                r.append([r[-1][0]+1,r[-1][1]])\n",
    "            elif i=='W':\n",
    "                if [r[-1][0],r[-1][1]-1] in r:\n",
    "                    return True\n",
    "                r.append([r[-1][0],r[-1][1]-1])\n",
    "            elif i=='N':\n",
    "                if [r[-1][0]-1,r[-1][1]] in r:\n",
    "                    return True\n",
    "                r.append([r[-1][0]-1,r[-1][1]])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        dirs = {\n",
    "            \"N\": (-1,0),\n",
    "            \"S\": (1,0),\n",
    "            \"E\": (0,1),\n",
    "            \"W\": (0,-1),\n",
    "        }\n",
    "        x, y = 0,0\n",
    "        vis = set([(x,y)])\n",
    "        for ch in path:\n",
    "            dx, dy = dirs[ch]\n",
    "            x, y =x+dx,y+dy\n",
    "            if(x,y)in vis:\n",
    "                return True\n",
    "            vis.add((x,y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        routesignal=[[0,0]]\n",
    "        route=[0,0]\n",
    "        for i in path:\n",
    "            if i==\"N\":\n",
    "                route[0]+=1\n",
    "                if route in routesignal:\n",
    "                    return True\n",
    "                else:\n",
    "                    routesignal.append(route.copy())\n",
    "            if i==\"S\":\n",
    "                route[0]-=1\n",
    "                if route in routesignal:\n",
    "                    return True\n",
    "                else:\n",
    "                    routesignal.append(route.copy())\n",
    "            if i==\"E\":\n",
    "                route[1]+=1\n",
    "                if route in routesignal:\n",
    "                    return True\n",
    "                else:\n",
    "                    routesignal.append(route.copy())\n",
    "            if i==\"W\":\n",
    "                route[1]-=1\n",
    "                if route in routesignal:\n",
    "                    return True\n",
    "                else:\n",
    "                    routesignal.append(route.copy())\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x, y, se = 0, 0, {(0, 0)}\n",
    "        for c in path:\n",
    "            if   c == 'N': y += 1\n",
    "            elif c == 'E': x += 1\n",
    "            elif c == 'S': y -= 1\n",
    "            else         : x -= 1\n",
    "            if (x, y) in se: return True\n",
    "            se.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x, y, se = 0, 0, {(0, 0)}\n",
    "        for c in path:\n",
    "            if   c == 'N': y += 1\n",
    "            elif c == 'E': x += 1\n",
    "            elif c == 'S': y -= 1\n",
    "            else         : x -= 1\n",
    "            if (x, y) in se: return True\n",
    "            se.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        point = [0,0]\n",
    "        points = ['0,0']\n",
    "        for p in path:\n",
    "            if p==\"N\":point[1]=point[1]+1\n",
    "            elif p==\"S\":point[1]=point[1]-1\n",
    "            elif p==\"E\":point[0]=point[0]+1\n",
    "            elif p==\"W\":point[0]=point[0]-1\n",
    "            #print(point)\n",
    "            tmp = str(point[0])+','+str(point[1])\n",
    "            print(tmp)\n",
    "            if tmp in points:return True\n",
    "            else:points.append(tmp)\n",
    "            print(points)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "\n",
    "        walkingPath = [[0, 0]]\n",
    "        for i in range(len(path)):\n",
    "            temp = copy.deepcopy(walkingPath[-1])\n",
    "            if path[i] == \"N\":\n",
    "                temp[1] += 1\n",
    "            elif path[i] == \"S\":\n",
    "                temp[1] -= 1\n",
    "            elif path[i] == \"W\":\n",
    "                temp[0] -= 1\n",
    "            elif path[i] == \"E\":\n",
    "                temp[0] += 1\n",
    "            print(walkingPath)\n",
    "            if temp in walkingPath:\n",
    "                return True\n",
    "\n",
    "            walkingPath.append(temp)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        s = [0, 0]\n",
    "        ans = [[0, 0]]\n",
    "        \n",
    "        for a in path:\n",
    "            if a == 'W': \n",
    "                s[0] -= 1\n",
    "            elif a == 'S': \n",
    "                s[1] -= 1\n",
    "            elif a == 'E': \n",
    "                s[0] += 1\n",
    "            elif a == 'N': \n",
    "                s[1] += 1\n",
    "            \n",
    "            if s in ans:\n",
    "                return True\n",
    "            else: \n",
    "                ans.append(s.copy())\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        c=0\n",
    "        d=0\n",
    "        e={(0,0):0}\n",
    "        flag=0\n",
    "        for x in path:\n",
    "            if x==\"N\":\n",
    "                c=c+1\n",
    "            elif x==\"S\":\n",
    "                c=c-1\n",
    "            elif x==\"E\":\n",
    "                d=d+1\n",
    "            else:\n",
    "                d=d-1\n",
    "            if (c,d) in e:\n",
    "                flag=1\n",
    "                break\n",
    "            else:\n",
    "                e[(c, d)] = 0\n",
    "        return flag==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        visited = [[0, 0]]\n",
    "        for p in path:\n",
    "            if p == 'N':\n",
    "                j += 1\n",
    "            elif p == 'S':\n",
    "                j -= 1\n",
    "            elif p == 'E':\n",
    "                i += 1\n",
    "            elif p == 'W':\n",
    "                i -= 1\n",
    "            if [i, j] in visited:\n",
    "                return True\n",
    "            visited.append([i, j])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        x, y, se = 0, 0, {(0, 0)}\n",
    "        for c in path:\n",
    "            if   c == 'N': y += 1\n",
    "            elif c == 'E': x += 1\n",
    "            elif c == 'S': y -= 1\n",
    "            else         : x -= 1\n",
    "            if (x, y) in se: return True\n",
    "            se.add((x, y))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        s = set()\n",
    "        x = y = 0\n",
    "        s.add((x, y))\n",
    "        for c in path:\n",
    "            if c == 'N':\n",
    "                y += 1\n",
    "            elif c == 'S':\n",
    "                y -= 1\n",
    "            elif c == 'E':\n",
    "                x += 1\n",
    "            else:\n",
    "                x -= 1\n",
    "            if (x, y) in s:\n",
    "                return True\n",
    "            s.add((x, y))\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isPathCrossing(self, path: str) -> bool:\r\n",
    "        directions = {\"N\": [0, 1], \"S\": [0, -1], \"E\": [1, 0], \"W\": [-1, 0]}\r\n",
    "        x, y, records = 0, 0, set([(0, 0)])\r\n",
    "        for c in path:\r\n",
    "            x += directions[c][0]\r\n",
    "            y += directions[c][1]\r\n",
    "            if (x, y) in records:\r\n",
    "                return True\r\n",
    "            \r\n",
    "            records.add((x, y))\r\n",
    "        \r\n",
    "        return False\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        start = [0, 0]\n",
    "        current = start\n",
    "        position = [start]\n",
    "        for i in range(len(path)):\n",
    "            if path[i] == \"N\":\n",
    "                current = [current[0], current[1] + 1]\n",
    "            elif path[i] == \"S\":\n",
    "                current = [current[0], current[1] - 1]\n",
    "            elif path[i] == \"E\":\n",
    "                current = [current[0] + 1, current[1]]\n",
    "            else:\n",
    "                current = [current[0] - 1, current[1]]\n",
    "            if current in position:\n",
    "                return True\n",
    "            else:\n",
    "                position.append(current)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        positionPoint = [[0,0]]\n",
    "        movingPoint =[0,0]\n",
    "        addPoint = []\n",
    "        for i in range(len(path)):\n",
    "            if path[i] == 'N':\n",
    "                movingPoint[1] += 1\n",
    "            if path[i] == 'S':\n",
    "                movingPoint[1] -= 1\n",
    "            if path[i] == 'E':\n",
    "                movingPoint[0] += 1\n",
    "            if path[i] == 'W':\n",
    "                movingPoint[0] -= 1\n",
    "            addPoint = copy.copy(movingPoint)\n",
    "            if addPoint not in positionPoint:\n",
    "                positionPoint.append(addPoint)\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        # record = []\n",
    "        # pos = [0, 0]\n",
    "        # record.append([pos[0], pos[1]])\n",
    "        # for way in path:\n",
    "        #     if way == 'N': pos[1] += 1\n",
    "        #     if way == 'S': pos[1] -= 1\n",
    "        #     if way == 'E': pos[0] += 1\n",
    "        #     if way == 'W': pos[0] -= 1\n",
    "        #     if pos in record: return True\n",
    "        #     record.append([pos[0], pos[1]])\n",
    "        # return False\n",
    "\n",
    "        s, coor = set(), (0, 0)\n",
    "        s.add(coor)\n",
    "        for p in path:\n",
    "            if p == 'N': x, y = 0, 1\n",
    "            elif p == 'S': x, y = 0, -1\n",
    "            elif p == 'E': x, y = 1, 0\n",
    "            else: x, y = -1, 0\n",
    "            coor = (coor[0] + x, coor[1] + y)\n",
    "            print(coor)\n",
    "\n",
    "            if coor in s: return True\n",
    "            s.add(coor)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        positionPoint = [[0,0]]\n",
    "        movingPoint =[0,0]\n",
    "        addPoint = []\n",
    "        for i in range(len(path)):\n",
    "            if path[i] == 'N':\n",
    "                movingPoint[1] += 1\n",
    "            if path[i] == 'S':\n",
    "                movingPoint[1] -= 1\n",
    "            if path[i] == 'E':\n",
    "                movingPoint[0] += 1\n",
    "            if path[i] == 'W':\n",
    "                movingPoint[0] -= 1\n",
    "            addPoint = copy.deepcopy(movingPoint)\n",
    "            if addPoint not in positionPoint:\n",
    "                positionPoint.append(addPoint)\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        directions = {\n",
    "            'N': [0, 1],\n",
    "            'S': [0, -1],\n",
    "            'E': [1, 0],\n",
    "            'W': [-1, 0]\n",
    "        }\n",
    "        coordinate = [[0, 0]]\n",
    "        cur_coordinate = [0, 0]\n",
    "        for i in path:\n",
    "            print(i, coordinate)\n",
    "            x, y = directions[i]\n",
    "            if [cur_coordinate[0] + x, cur_coordinate[1] + y] in coordinate:\n",
    "                return True\n",
    "            else:\n",
    "                coordinate.append([cur_coordinate[0] + x, cur_coordinate[1] + y])\n",
    "                cur_coordinate = [cur_coordinate[0] + x, cur_coordinate[1] + y]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isPathCrossing(self, path: str) -> bool:\r\n",
    "        directions = {\"N\": [0, 1], \"S\": [0, -1], \"E\": [1, 0], \"W\": [-1, 0]}\r\n",
    "        x, y, records = 0, 0, set([(0, 0)])\r\n",
    "        for c in path:\r\n",
    "            x += directions[c][0]\r\n",
    "            y += directions[c][1]\r\n",
    "            if (x, y) in records:\r\n",
    "                return True\r\n",
    "            \r\n",
    "            records.add((x, y))\r\n",
    "        \r\n",
    "        return False\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "        q=Counter([(0,0)])\n",
    "        e={\"N\":0,\"E\":1,\"S\":2,\"W\":3}\n",
    "        f=[[-1,0],[0,1],[1,0],[0,-1]]\n",
    "        i,j=0,0\n",
    "        for x in path:\n",
    "           x=f[e[x]]\n",
    "           print(x)\n",
    "           i+=x[0]\n",
    "           j+=x[1]\n",
    "           if (i,j) in q:\n",
    "               return True\n",
    "           print(q)    \n",
    "           q[(i,j)]+=1    \n",
    "        return False    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:        \n",
    "        c=[0,0]\n",
    "        point={(0,0):1}\n",
    "        for i in path:\n",
    "            if i=='N':\n",
    "                c[0]+=1                \n",
    "            elif i=='S':\n",
    "                c[0]-=1                \n",
    "            elif i=='E':\n",
    "                c[1]+=1\n",
    "            elif i=='W':\n",
    "                c[1]-=1                \n",
    "            point[(c[0],c[1])]=point.get((c[0],c[1]),0)+1\n",
    "        for v in point.values():\n",
    "            if v>=2:\n",
    "                return True                            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPathCrossing(self, path: str) -> bool:\n",
    "      list_1 = [(0,0)]\n",
    "      for i in path:\n",
    "        if i == 'N':\n",
    "          list_1.append((list_1[-1][0]+1,list_1[-1][1]))\n",
    "        elif i == 'S':\n",
    "          list_1.append((list_1[-1][0]-1,list_1[-1][1])) \n",
    "        elif i == 'E':\n",
    "          list_1.append((list_1[-1][0],list_1[-1][1]+1))\n",
    "        elif i == 'W':\n",
    "          list_1.append((list_1[-1][0],list_1[-1][1]-1))\n",
    "      return len(list_1) != len(set(list_1))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
